# Read the solution [here](https://quastor.org/cracking-the-coding-interview/stacks-and-queues/stack-of-plates)

# Stack of Plates

## Cracking the Coding Interview (CTCI) 3.3

<br />

## Question

Imagine a stack of plates. If the stack gets too high then it will become unstable and topple over. Therefore, when stacking plates we create a new stack after a certain number of plates.

<br />

Implement a data structure that mimics this behavior. `SetOfStacks` should be composed of several stacks and it should create a new stack once the previous one exceeds a certain threshold.

<br />

`SetOfStacks.push()` and `SetOfStacks.pop()` should behave identically to if the data structure was just a single stack.

<br />

<details>
  <summary>Solution</summary>

  
We'll design the class to have a `push` and `pop` method, so the API is identical to a normal stack.

  <br />

  In order to instantiate the class, the user will have the option of providing the capacity of the stacks. The capacity must be a positive number (greater than 0). We set the default capacity to an arbitrary number (we picked 10).

  <br />

  We will represent the data structure internally with a 2 dimensional list. Everytime one list reaches capacity, we'll add another.

  <br />

  The list allows us to do `push` and `pop` operations in $$O(1)$$ time.

  <br />

  With our `push` method, we first check to make sure that our current stack (the last list in our 2-D list) is not at capacity.

  <br />

  If it is, then we add a new empty list as our current stack.

  <br />

  Then, we can just append the value to our current stack.

  <br />

  In `pop`, we first check to make sure that there is at least one value in our data structure. If not, we throw an `IndexError`.

  <br />

  Otherwise, we can just pop the last value and return it.

  <br />

  `push` and `pop` both take $$O(1)$$ time.
  
  ```python
  class SetOfStacks:
      def __init__(self, capacity = 10):
          if capacity < 1:
              raise ValueError("capacity must be at least 1")
          
          self.capacity = capacity
          self.stacks = [[]]
      
      def push(self, val):
          if len(self.stacks[-1]) == self.capacity:
              self.stacks.append([])
          
          self.stacks[-1].append(val)
      
      def pop(self):
          if len(self.stacks[-1]) == 0:
              if len(self.stacks) == 1:
                  raise IndexError("pop from empty stack")
              else:
                  self.stacks.pop()
          
          return self.stacks[-1].pop()
  ```

</details>

<br />

## Follow Up

Implement a function `popAt(index)` which performs a pop operation on a specific stack in your set of stacks.

<br />

<details>
  <summary>Solution</summary>

  There are two main ways you can implement this.

  <br />

  One way is to just pop the element out of the specific stack without performing a left shift operation (shifting over the elements in the stacks that come after this one left by 1).

  <br />

  If we don't perform the left shift operation, this particular stack will be smaller than capacity while stacks to the left (stacks that come *after*) might be at full capacity. This may violate assumptions about the `SetOfStacks` data structure.

  <br />

  THe other way of implementing this is with the left shift operation. Whenever we `popAt` a stack that is not the last stack, we shift over 1 element from all the stacks on the left so that all of the stacks (excluding the last one) are at full capacity.

  <br />

  The issue with the left shift operation is that it makes our `popAt` function more computationally expensive. The left shift operation will take $$O(n)$$ time every time it's performed.

  <br />

  We will implement our `popAt` function *with* a left shift operation.

  <br />

  The left shift operation will be implmeneted with a `while` loop. We start off on the stack we just popped from and append the first element of the next stack (while popping the first element off that stack). We continue with the next stack until we've reached the last stack.

  <br />

  If, after our left shift operation, the last stack in our `SetOfStacks` is empty, then we `pop` off that stack.

  <br />

  `popAt` takes $$O(n)$$ time.

  ```python
  class SetOfStacks:
    def __init__(self, capacity = 10):
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        
        self.capacity = capacity
        self.stacks = [[]]
    
    def push(self, val):
        if len(self.stacks[-1]) == self.capacity:
            self.stacks.append([])
        
        self.stacks[-1].append(val)
    
    def pop(self):
        if len(self.stacks[-1]) == 0:
            if len(self.stacks) == 1:
                raise IndexError("pop from empty stack")
            else:
                self.stacks.pop()
        
        return self.stacks[-1].pop()
    
    def _leftShift(self, stack):
        while stack + 1 < len(self.stacks):
            self.stacks[stack].append(self.stacks[stack + 1].pop(0))
            stack += 1
        if len(self.stacks[-1]) == 0:
            self.stacks.pop()

    def popAt(self, stack):
        if stack >= len(self.stacks):
            raise IndexError("stack index out of range")
        
        if len(self.stacks[stack]) == 0:
            raise IndexError("pop from empty stack")
        
        returnValue = self.stacks[stack].pop()

        self._leftShift(stack)
        return returnValue
  ```
</details>